package com.ljy.my_study.leetcode.平衡二叉树;

import java.util.ArrayList;
import java.util.List;

/** 
* @author James
* @date 2018年9月17日 
*/
public class TestMain {
//	给定一个二叉树，判断它是否是高度平衡的二叉树。
//
//	本题中，一棵高度平衡二叉树定义为：
//
//	一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
	
	public static void main(String[] args) {
		System.out.println(Math.pow(2, 2));
		Integer[] arr= {3,9,20,null,null,15,7};
		Integer[] arr1= {1,2,2,3,3,1,null,4,4};
		TestMain testMain=new TestMain();
		TreeNode head=testMain.createTreeNode(arr1);
		System.out.println(head.toString());
		System.out.println("--------------------------");
		System.out.println(testMain.isBalanced(head));
//		int max=0;
//		int n=0;
//		System.out.println(testMain.getHeight(head, n, max));
	}
	
	public TreeNode createTreeNode(Integer[] arr) {
		if(arr.length==0)return null;
		TreeNode head=null;
		int len=arr.length;
		
		List<TreeNode> treeNodeList=new ArrayList<>();
		for(int i=0;i<arr.length;i++) {
			if(arr[i]==null) {
				treeNodeList.add(null);
			}else {
				treeNodeList.add(new TreeNode(arr[i]));
			}
		}
		head=treeNodeList.get(0);
		for(int i=0;i<treeNodeList.size();i++) {
			if(treeNodeList.get(i)!=null) {
				if((i+1)*2-1<len&&arr[(i+1)*2-1]!=null) {
					treeNodeList.get(i).left=treeNodeList.get((i+1)*2-1);
				}
				if((i+1)*2<len&&arr[(i+1)*2]!=null) {
					treeNodeList.get(i).right=treeNodeList.get((i+1)*2);
				}
			}
		}
		
		
		return head;
	}
	
	public boolean isBalanced(TreeNode root) {
		if(root==null) {
			return true;
		}
		TreeNode node=root;
		int leftMax=getHeight(root.left,0,0);
		int rightMax=getHeight(root.right,0,0);
		if(leftMax-rightMax>=2||rightMax-leftMax>=2) {
			return false;
		}
		if(!isBalanced(node.left)) {
			return false;
		}
		if(!isBalanced(node.right)) {
			return false;
		}
		return true;
	}
	
	public int getHeight(TreeNode root,int n,int max) {
		if(root==null) {
			return max;
		}else {
			n++;
			if(n>max) {
				max=n;
			}
		}
		int leftMax=getHeight(root.left,n,max);
		int rightMax=getHeight(root.right,n,max);
		if(leftMax>max) {
			max=leftMax;
		}
		if(rightMax>max) {
			max=rightMax;
		}
		return max;
	}
	
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode(int x) { val = x; }
		@Override
		public String toString() {
			return val+"";
		}
	}
}
